package com.mars.algorithm;

import com.sun.org.apache.xml.internal.utils.Trie;

/**
 * @Author King
 * @create 2020/7/30 11:47
 */
public class KingSort {

    public static void main(String[] args) {
        int[] s = new int[]{14, 6, 8, 12, 2, 34, 9, 33, 17};
        //maoPaoSort(s);
        insertSort(s);
        //quickSort(s, 0, s.length - 1);


        Trie trie = new Trie();
        trie.put("she", "sdsfgfd");
        Object v = trie.get("she");
        System.out.println("sfdsf");
    }


    private static int[] maoPaoSort(int[] source) {
        if (source.length == 0) {
            return null;
        }
        for (int j = 0; j < source.length; j++) {
            for (int i = 0; i < source.length - 1; i++) {
                if (source[i] > source[i + 1]) {
                    int tmp = source[i + 1];
                    source[i + 1] = source[i];
                    source[i] = tmp;
                }
            }
        }
        return source;
    }


    private static int[] insertSort(int[] source) {

        for (int i = 1; i < source.length; i++) {
            int tmp = source[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (source[j] > tmp) {
                    source[j + 1] = source[j];
                } else {
                    break;
                }
            }
            source[j + 1] = tmp;
        }
        return source;
    }


    private static void quickSort(int[] s, int left, int right) {
        if (null == s || left >= right || s.length <= 1) {
            return;
        }
        //获取基准数
        int p = partition(s, left, right);
        //对分区递归排序--左边
        quickSort(s, left, p - 1);
        //对分区递归排序--右边
        quickSort(s, p + 1, right);
    }


    private static int partition(int[] s, int left, int right) {
        //找基准tmp
        int tmp = s[left];
        while (left < right) {
            while (s[right] >= tmp && left < right) {
                right--;
            }
            s[left] = s[right];
            while (s[left] <= tmp && left < right) {
                left++;
            }
            s[right] = s[left];
        }
        s[right] = tmp;
        return right;
    }


}
